Traditional grayscale and binary compression techniques analyze image data stream a single-bit at a time to generate compressed image data. Conventional grayscale image encoding techniques use run-length encoding techniques that can not typically be used effectively to compress binary image data because the concept of similar pixel color groupings at a byte-level in binary image data is not present. And, traditional binary image data compression techniques to replace juxtaposed pixels that match predetermined bit patterns in a dictionary are computationally intensive—often resulting in slow response times in software implementations, and complex and expensive to implement in hardware.
For instance, conventional color and grayscale data compression techniques typically analyze an image data stream a single-bit at a time to determine if a sequential number of pixels, wherein each pixel is typically defined by 8-24 bits of data, have respective color values that correspond to a current pixel. When multiple sequential pixels with the same color are identified, a code is inserted into a compressed data stream to describe a color value and a repeat length. In this manner, multiple bytes (e.g., hundreds or even thousands of bytes) of color data can be represented with a couple of bytes of encoded data in a compressed data stream. This type of image data compression is called run-length encoding. Run-length encoding is often used to compress color and grayscale data because colors tend to occur juxtaposed or side-by-side to one another in color and grayscale images.
Run-length encoding of side-by-side pixels representing a same color, as often performed in the compression of color and grayscale image data, does not work very well when considering the compression of binary image data. This is because a binary pixel is represented with a single bit of data, not 8-24 bits of data that are byte-aligned. This means that a byte or 8-bits represent 8 separate pixels of color. Because only a single bit is used to represent a pixel, binary images typically do not exhibit enough color similarity from bit-to-bit to efficiently leverage the run-length encoding techniques.
For example, consider that color data that is represented with 8-24 bits of data per pixel are often reduced to binary or bi-level image data (2-bits per pixel) by halftoning procedures to change the data's attributes to conform to specific printer, marker, or imaging device output requirements. Halftones are created through a process called dithering, in which a density and pattern of black and white dots are varied to simulate different shades of gray. Such patterns of black and white dot values do not typically exhibit enough color similarity from bit-to-bit to efficiently leverage the run-length encoding techniques used to compress color and grayscale images, which represent pixels with 8-24 bits. Because of this limitation of run-length encoding techniques when it comes to the compression of binary data, a number of other conventional compression techniques are used to compress binary image data (certain ones of these techniques may also be used to compress grayscale data).
For example, conventional binary compression techniques (e.g., those based on an international standard called JBIG or Lempel-Ziv (LZ) algorithms) typically analyze image data a single-bit at a time. JBIG attempts to guess the bit, and then code the error of the bit with the guess using an arithmetic coding. Whereas LZ operates on single-bits attempting to identify pre-determined bit-patterns (i.e., patterns stored in a pattern dictionary). Once such a pattern is identified, it is replaced in the original image data with a corresponding tag that has a smaller bit footprint than the identified bit pattern. The binary bit-pattern dictionary can be expanded. For instance if a certain number of pixels have been read without a corresponding dictionary pattern match, those unmatched pixels can be stored in the dictionary as another pattern. Using such techniques binary data can be compressed. However, these binary compression techniques are problematic for a number of reasons.
For example, even though a binary image bit-pattern dictionary can be expanded to include otherwise unrepresented bit patterns, it can be appreciated that the range of binary image data that can be effectively compressed using these techniques decreases rapidly as image complexity (i.e., image entropy) increases. Additionally, hardware implementations of such binary compression techniques are typically very costly to implement and require highly skilled technicians to implement complex timing algorithms. Moreover, software implementations of conventional binary compression techniques typically result in exceedingly slow binary compression response times due to the computationally intensive nature of analyzing image data for complex bit-patterns a single-bit at a time.
The following arrangements and procedures address these and other problems associated with compressing grayscale and binary data.